//: [Previous](@previous)

/*:
 ### leetcode上第219号问题：Contains Duplicate II
 ```
 给出⼀个整形数组nums和⼀个整数k，是否存在索引i和j，使得nums[i] == nums[j] 且i和j之间的差不超过k
 Example 1:
 Input: nums = [1,2,3,1], k = 3
 Output: true.
 Example 2:
 Input: nums = [1,0,1,1], k = 1
 Output: true
 Example 3:
 Input: nums = [1,2,3,1,2,3], k = 2
 Output: false
 ```
 */

// 直接遍历 Leetcode 超时 ……—^-
// O(n^2)
// O(1)
func Solution(_ nums: [Int], _ k: Int) -> Bool {
    
    for i in 0..<nums.count {
        let end = min(i+k+1, nums.count)
        for j in i+1..<end {
            if nums[i] == nums[j] {
                return true
            }
        }
    }
    
    return false
}

print(Solution([1,2,3,1], 3))
print(Solution([1,0,1,1], 1))
print(Solution([1,2,3,1,2,3], 2))

// 使用临时数组保存匹对 Leetcode 超时 ……—^-
// O(n)
// O(n)
func Solution2(_ nums: [Int], _ k: Int) -> Bool {
    
    var result: [Int] = []
    
    for i in 0..<nums.count {
        if result.first(where: { $0 == nums[i] }) != nil {
            return true
        }
        
        result.append(nums[i])
        if result.count > k {
            result.removeFirst()
        }
    }
    
    return false
}
print("\n")
print(Solution2([1,2,3,1], 3))
print(Solution2([1,0,1,1], 1))
print(Solution2([1,2,3,1,2,3], 2))

// 使用Set  Best++
// 当 i > k 时， 删除 i-k+1的元素
// O(n)
// O(1)
func Solution3(_ nums: [Int], _ k: Int) -> Bool {
    
    var set = Set<Int>()
        
    for i in 0..<nums.count {
        if i > k {
            set.remove(nums[i-k-1])
        }
        
        let result: (inserted: Bool, memberAfterInsert: Int) = set.insert(nums[i])
        
        print(set)
        
        if !result.inserted {
            return true
        }
        
    }
    
    return false
}

print("\n")
print(Solution3([1,2,3,1], 3))
print(Solution3([1,0,1,1], 1))
print(Solution3([1,2,3,1,2,3], 2))

//: [Next](@next)
